package first_practice;

import java.util.ArrayList;
import java.util.List;

/**
 * @author ZhiWen Ren
 * @version 1.0
 * @description: LeetCode-73-矩阵置零
 * @date 2025/3/28 15:35
 */

// 方法一：
/* public class Solution73 {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        List<int[]> zero = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    // 将所有0元素的位置保存在List中，再依次改变
                    zero.add(new int[]{i, j}); // 匿名数组
                }
            }
        }
        for (int[] ele : zero) {
            becomeZero(matrix, ele[0], ele[1]);
        }
    }

    public void becomeZero(int[][] matrix, int i, int j) {
        for (int row = 0; row < matrix.length; row++) {
            matrix[row][j] = 0;
        }
        for (int col = 0; col < matrix[0].length; col++) {
            matrix[i][col] = 0;
        }
    }
}
*/

// 方法二：时间复杂度O(m*n);空间复杂度O(m+n)
/*
public class Solution73 {
    public void setZeroes(int[][] matrix) {


        int m = matrix.length, n = matrix[0].length;
        boolean[] rowZero = new boolean[m]; // 额外用两个数组保存0元素出现的行和列, 空间复杂度0(m+n)
        boolean[] colZero = new boolean[n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(matrix[i][j] == 0){
                    rowZero[i] = true;
                    colZero[j] = true;
                }
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(rowZero[i] || colZero[j]){
                    matrix[i][j] = 0;
                }
            }
        }

    }
}
*/

// 方法三：时间复杂度O(m*n);空间复杂度O(1)
public class Solution73{
    public void setZeros(int[][] matrix){
        int m = matrix.length, n = matrix[0].length;
        boolean firstRowZero = false, firstColZero = false;
        // 用matrix的第一行和第一列存储0元素的信息,第一行和第一列出现0需要额外判断一下
        for(int i = 0; i < m; i++){
            if(matrix[i][0] == 0){
                firstColZero = true;
                break;
            }
        }

        for(int i = 0; i < n; i++){
            if(matrix[0][i] == 0){
                firstRowZero = true;
                break;
            }
        }

        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                if(matrix[i][j] == 0){
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if(matrix[i][0] == 0 || matrix[0][j] == 0){
                    matrix[i][j] = 0;
                }
            }
        }

        if(firstColZero){
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }

        if(firstRowZero){
            for (int i = 0; i < n; i++) {
                matrix[0][i] = 0;
            }
        }

    }
}